package swardToOffer.struct_2_string;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;

/**
 * @Author ChanZany
 * @Date 2021/5/24 8:47
 * @Version 1.0
 * 面试题38：字符串的排列
 * 题目：输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，
 * 则打印出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。
 * 全排列、子集的思路都是回溯法，会避免重复，需要在此基础上进行剪枝（Set）
 */
public class StringPermutation {
    HashSet<String> set = new HashSet<>();
    List<String> res = new ArrayList<>();
    char[] c;

    //优化：通过交换来节省创建cur的空间
    public String[] permutation(String s) {
        c = s.toCharArray();
        dfs(0);
        return res.toArray(new String[0]);
    }

    private void dfs(int index) {
        if (index==c.length-1){
            res.add(String.valueOf(c)); //添加排列方案
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for (int i = index; i < c.length; i++) {
            if (set.contains(c[i])) continue;//重复，则剪枝
            set.add(c[i]);
            swap(i,index);
            dfs(index+1);
            swap(i,index);
        }
    }
    void swap(int a, int b) {
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }


    public String[] permutation1(String s) {
        if (s.length() == 0) return null;
        char[] chs = s.toCharArray();
        boolean[] visited = new boolean[chs.length];
        List<StringBuilder> res = new ArrayList<>();
        dfs(chs, new StringBuilder(), visited, res);
        String[] rets = new String[res.size()];
        for (int i = 0; i < res.size(); i++) {
            rets[i] = res.get(i).toString();
        }
        return rets;
    }

    private void dfs(char[] chs, StringBuilder cur, boolean[] visited, List<StringBuilder> res) {
        if (cur.length() == chs.length) {
            if (set.contains(cur.toString())) return;
            res.add(new StringBuilder(cur));
            set.add(cur.toString());
            return;
        }
        for (int i = 0; i < chs.length; i++) {
            if (!visited[i]) {
                visited[i] = true;
                cur.append(chs[i]);
                dfs(chs, cur, visited, res);
                visited[i] = false;
                cur.deleteCharAt(cur.length()-1);
            }
        }
    }


    public static void main(String[] args) {
        StringPermutation Main = new StringPermutation();
        System.out.println(Arrays.toString(Main.permutation("abb")));
    }
}
